import java.util.Scanner;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 11 - 21
 * Time: 10:54
 */
//牛客 斐波那契凤尾
public class Solution19 {
    //这个方法是输入一次算一次，这个方法效率慢会运行超时
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int border = -1;
            if (n == 1) {
                System.out.println(1);
            }else if(n == 2) {
                System.out.println(2);
            } else {
                int[] dp = new int[n + 1];
                dp[1] = 1;
                dp[2] = 2;
                for (int i = 3; i <= n; i++) {
                    int x = dp[i - 1] + dp[i - 2];
                    if(border == -1 && x > 999999) {
                        border = i + 1;
                    }
                    dp[i] = x % 1000000;//重点，当斐波那契数太大时，long也会存不下，所以用dp数组存斐波那契数时只存斐波那契数的后六位
                }
                if(border == -1) {
                    System.out.printf("%d\n", dp[n]);
                }else {
                    System.out.printf("%06d\n", dp[n]);
                }
            }
        }
    }

    //这个方法是把所有结果算好了存储下来，输入的时候直接查，这个方法效率快不会运行超时
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] dp = new int[100001];
        int border = -1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= 100000; i++) {
            int x = dp[i - 1] + dp[i - 2];
            if (border == -1 && x > 999999) {
                border = i + 1;
            }
            dp[i] = x % 1000000;//重点，当斐波那契数太大时，long也会存不下，所以用dp数组存斐波那契数时只存斐波那契数的后六位
        }
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            if (n < border) {
                System.out.printf("%d\n", dp[n]);
            } else {
                System.out.printf("%06d\n", dp[n]);
            }
        }
    }
}
